#include <stdio.h>
#include <stdlib.h>
 struct term {
	float coe;
	float exp;
	struct term *next;
};
struct term* allocate(size_t size) {
    struct term* ptr = (struct term*) malloc (size);
    if (ptr == NULL) {
        fprintf(stderr, "内存分配失败");
        exit(EXIT_FAILURE);
    }
    return ptr;
}
struct term* createterm (float coe, float exp) {
	struct term* newterm = allocate (sizeof (struct term));
	newterm->coe = coe;
	newterm->exp = exp;
	newterm->next = NULL;
	return newterm;
}
void insertterm (struct term** head, struct term* newterm) {
	if (*head == NULL || (*head)->exp < newterm->exp) {
		newterm->next = *head;
		*head = newterm;
	} else {
		struct term* current = *head;
		while (current->next != NULL && current->next->exp > newterm->exp) {
			current = current->next;
		}
		newterm->next = current->next;
		current->next = newterm;
	}
}
void print (struct term* head) {
	struct term* current = head;
	while (current != NULL) {
		printf("%.2fX^%.2f", current->coe, current->exp);
		current = current->next;
		if (current != NULL) {
			printf(" + ");
		}
	}
	printf("\n");
}
struct term* add (struct term* p1, struct term* p2) {
	struct term* head = NULL;
	while (p1 != NULL && p2 != NULL) {
		if (p1->exp > p2->exp) {
			insertterm(&head, createterm(p1->coe, p1->exp));
			p1 = p1->next;
		} else if (p1->exp < p2->exp) {
			insertterm(&head, createterm(p2->coe, p2->exp));
			p2 = p2->next;
		} else {
			float sum = p1->coe + p2->coe;
			if (sum != 0) {
				insertterm(&head, createterm(sum, p1->exp));
			}
			p1 = p1->next;
			p2 = p2->next;
		}
	}
	while (p1 != NULL) {
		insertterm(&head, createterm(p1->coe, p1->exp));
		p1 = p1->next;
	}
	while (p2 != NULL) {
		insertterm(&head, createterm(p2->coe, p2->exp));
		p2 = p2->next;
	}
	return head;
}
void freelist(struct term* head) {
	struct term* current = head;
	while (current != NULL) {
		struct term* temp = current;
		current = current->next;
		free(temp);
	}
}
 int main() {
	struct term* p1 = NULL;
	printf("请输入多项式1的项数：");
	int n1;
	scanf("%d", &n1);
	for (int i =0; i < n1; i++) {
		float coe, exp;
		printf("请输入第%d项的系数和指数（空格分开）：",i+1);
		scanf("%f %f",&coe, &exp);
		insertterm(&p1, createterm(coe,exp));
	}
	struct term* p2 = NULL;
	printf("请输入多项式2的项数：");
	int n2;
	scanf("%d", &n2);
	for (int i =0; i < n2; i++) {
		float coe, exp;
		printf("请输入第%d项的系数和指数（空格分开）：",i+1);
		scanf("%f %f",&coe, &exp);
		insertterm(&p2, createterm(coe,exp));
	}
	struct term* result = add(p1,p2);
	printf("多项式1：");
	print(p1);
	printf("多项式2：");
	print(p2);
	printf("相加结果：");
	print(result);
	freelist(p1);
	freelist(p2);
	freelist(result);
}